/*
 * Linkedlist.c
 *
 *  Created on: 2011-11-28
 *      Author: tracl01
 */
#include <stdio.h>
#include <stdlib.h>
typedef int Elemtype;
typedef struct {
	Elemtype data;
	struct LNode *next;
}LNode, *Linklist;			//将Linkedlist直接定义成指针，对于链表这种结构比较合适

int initLinklist(Linklist *L){	//why可以将指针的指针不经初始化就传递进来？因为传递的是个地址
	*L = (Linklist)malloc(sizeof(LNode));	//L是指针的指针，*L就是指向一个Lnode结构体的指针
	if (!*L) {
		exit(EXIT_FAILURE);
//		printf("hello");
	}
	(*L)->next = NULL;
	return EXIT_SUCCESS;
}

int getElem(Linklist L, int i, Elemtype *elem){
	Linklist p;
	p = L->next;	//p工作指针统一初始化指向第一个元素
	int j = 1;
	while(p && j<i){
		p = p->next;
		j++;
	}
	if (!p || j>i) {		//由于i为形参，对形参的合法性的判断是一个基本原则
		return EXIT_FAILURE;//将不合法条件放在if里更合适，判断不合法总比合法简单可靠
	} else {				//对于按index取元素，一定少不了判断是否合法；
		elem = p->data;		//因为链表没有记录其长度，故放在查找完后判断
		return EXIT_SUCCESS;
	}
}

int insertLinklist(Linklist L, int i, Elemtype e){
	Linklist p = L;
	int j = 0;				//统一规律:p和j关系恒为p指向第j个结点；第0个结点为头结点
	while(p && j<i-1){			//j的变化限制即使p运动到停止的结点
		p = p->next;			//那对程序首要分析的当时工作指针从哪开始到哪停
		j++;
	}
	if (!p || j>i-1) {
		return EXIT_FAILURE;
	} else {
		Linklist newnode = (Linklist)malloc(sizeof(LNode));
		newnode->data = e;
		newnode->next = p->next;
		p->next = newnode;
		return EXIT_SUCCESS;
	}
}

int deleteLinklist(Linklist L, int i, Elemtype *e){
	Linklist p = L;
	int j = 0;
	while(p->next && j<i-1){	//p依然与j保持一致，但判断上却要针对具体情况，此处确保所删结点不为空
		p = p->next;			//定位置和判断结点是可分离的，插入和删除需要判断结点不一样
		j++;
	}
	if (!p->next || j>i-1) {
		return EXIT_FAILURE;
	} else {
		Linklist q = p->next;
		e = q->data;
		p = q->next;
		free(q);
		return EXIT_SUCCESS;
	}
}

void mergeLinklist(Linklist La, Linklist Lb, Linklist Lc){	//我对链表归并理解几乎全错了
	Linklist pa,pb,pc;
	pa = La->next; pb = Lb->next; pc = Lc;	//只读结点的话，初始为第一个元素最好；需要操作结点的话
	while(pa && pb){			//当初始为头结点，如pc
		if (pa->data <= pb->data) {
			pc->next = pa;pa = pa->next;	//链表归并可以直接使用原有结点，所以不用分配新结点
		} else {
			pc->next = pb;pb = pb->next;
		}
	}
	pc->next = (pa ? pa : pb);				//对于链表，不同链表的相同类型的结点是可以直接互指的
	/*
	while(pa->data) {
		pc->data = pa->data;pa = pa->next;pc = pc->next;
	}
	while(pb->data) {
		pc->data = pb->data;pb = pb->next;pc = pc->next;
	}
	*/
}
/*
int main(void){
	printf("hello world！问题出在哪里？为什么合并的元素只有一半？\n");
	Linklist La,Lb,Lc,p;
	initLinklist(&La);			//不能将未初始化的指针直接作为给函数形参
	initLinklist(&Lb);
	initLinklist(&Lc);
	int i;
	for (i = 0; i < 5; ++i) {
		insertLinklist(La,i+1,i);
		insertLinklist(Lb, i+1, i+5);
	}
	mergeLinklist(La, Lb, Lc);
	p = Lc->next;
	while(p){
		printf("%d ", p->data);
		p = p->next;
	}
	return EXIT_SUCCESS;
}
*/
